package QuestionDaily;

import utils.TreeNode;

public class bstToGst_1038 {
    /**
     *给定一个二叉搜索树 root (BST)
     * 请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。
     */
    public TreeNode bstToGst(TreeNode root) {
        root.val=dfs(root);
        return root;
    }
    int dfs(TreeNode node) {
        /**
         * 上层节点只需要直接加上右子树的头节点即可，左子树的头节点满足条件也可以加上
         * 因为左子树的和都小于该节点，子树内必然没有节点大于该节点
         * md  写了半天发现理解错了题意，我以为是该节点的左右子树内
         * 没想到题意是整个树里所有大于该节点的数和
         */
        if(node==null)
            return 0;
        int sumLeft=0;
        int sumRight=0;
        int val= node.val; //标记当前节点的值
        sumLeft=dfs(node.left);
        if(node.left!=null)
            node.left.val=sumLeft;

        sumRight=dfs(node.right);
        if (node.right != null)
            node.right.val = sumRight;

        int num=0;
        if(sumLeft>=val)
            num+=sumLeft;
        num+=sumRight;
       return val+num;
    }


    /**
     *  也不难，从右子树向左进行递归
     *  因为右子树的所有值都大于左子树
     */
    private int s = 0;

    public TreeNode bstToGst2(TreeNode root) {
        dfs2(root);
        return root;
    }

    private void dfs2(TreeNode node) {
        if (node == null) {
            return;
        }
        dfs2(node.right); // 递归右子树
        s += node.val;
        node.val = s; // 此时 s 就是 >= node.val 的所有数之和
        dfs2(node.left); // 递归左子树
    }
}
